945 476037
56622361 521506250 599016932 541909906 427732189 833236956 261001942 256395660 478705411 928025476 675463865 891433985 196320631 960829508 391721770 900518004 820955308 104007618 15318669 245962446 963113494 940396104 587839114 640888794 317906607 653311301 887406732 172105674 267356531 135051722 357272641 7012528 376035300 523617550 404573725 519908102 408420998 610782443 643082198 323746855 765844836 164715102 972038889 144331475 791534217 326714378 370740500 794251695 447923848 736578230 863930586 909785027 258691317 655073739 274182146 157390074 925606634 972290519 190716440 932987045 434937731 742366476 643415787 228712440 493210210 497388993 641632013 480371340 846601259 861442288 290303575 212040412 823249673 122078391 243732066 819111112 171275560 586277591 386725134 484277780 844627769 892207928 988973311 708840170 294793457 186176099 735952411 475623508 28869001 306738182 620660749 156731075 812770879 237534068 478872261 267980427 899320532 521884706 513244918 179362404 539606029 723958315 363223191 718122475 291074611 191644365 378768227 155139102 574798226 559887594 269227353 365044196 406380285 567833480 754767676 165754499 395192904 298404946 293359891 110049832 56844493 770553364 977693354 812816483 648659432 682737986 461450768 688265384 574369147 545813618 667446295 686968014 728212075 740644573 65843416 96987540 40321313 54846178 302071852 142555927 406191113 500284036 286233651 527728990 21422102 763568615 292670417 287324367 11554620 137969622 620989228 524169910 348878581 519968832 655461936 1980357 507338429 446257335 904909579 711298702 631194262 215088368 563030193 45838347 995285893 837425989 216323417 920112151 980830227 265387830 818075389 87492083 192456396 345675235 480228830 799129282 811196611 779827348 35425535 768553996 361006093 818376498 682015397 396664383 714984513 312570059 174339293 741839145 548373759 250222097 121546230 338695808 622331493 33896411 330367747 259338842 333754779 803433379 98482266 383017909 521584457 816547847 480641047 674714864 128509468 232538953 931956890 554872912 884181829 995309007 897802500 971016317 372231929 945966243 863376831 700132610 535036658 150667251 297357555 639805136 43295468 180710802 621321489 484989115 219283753 481201014 707539276 469228027 645731566 885077560 821896219 775247021 617316612 478286743 210810809 676562000 665861687 222050037 505043621 144271945 736009178 859497432 424095779 4261471 584873026 416317546 855764152 171202367 824825158 64485370 834605745 650087673 609195206 900311929 208554653 105254785 325338401 912996350 510667727 223713583 795422653 280707395 554847453 816545087 939870594 989749285 36567075 816137298 81721183 79228711 838891073 718597355 382615748 26484464 449624729 232353779 918764583 699044040 12964306 549556022 530181503 876659487 509385816 962630116 765642444 83350023 430825689 543278865 933200013 668264373 815310025 426440245 837386312 305036548 703045855 47889836 328848646 5888497 751252886 102330166 723000275 979786272 684741037 931317881 556393026 217307990 814066855 541174650 904453864 504036860 803089228 438523688 27199453 304492963 636967974 583254481 89335102 763127162 930854917 363597739 674099117 511456474 826311804 247820109 596110543 983836603 888280673 421970995 383582669 616567612 82979921 392018749 620605396 177187871 558413097 794994480 828795029 87427914 51577486 949513523 27309765 42160711 76035430 833051476 912904350 414422468 226968157 203016449 953897565 222403604 956276322 175119759 199969474 228349869 604831527 700106423 953017235 532913064 877364132 909352212 779101208 385687621 863149204 9512614 573157280 971326820 985370870 532768593 860713980 795603212 80022157 591947615 481697791 680952295 785579105 981800954 564219908 90039748 425881916 784375219 411271271 145707029 525622830 217906430 311947274 993214062 392562442 978371251 441103058 117604620 409533670 574331535 27425832 47145804 540534431 575103409 36666233 245426223 714774867 620263709 461823670 565856477 991131365 234416700 982394581 634963742 763304572 648769882 683378254 496213474 569753860 40065063 191216030 119329723 637994411 286829111 873737160 304823646 609623141 250712450 272240334 3653158 621939305 530297572 893573180 464129169 924674226 238543006 377577374 283463873 338462848 875688659 899700998 536255227 943702996 652105228 77065095 957098539 58366455 365875125 613752764 926431327 936741875 713753757 396806210 54504264 64241944 923347834 519501881 774234300 772614009 929322339 746810823 653846838 931272813 601624660 342745749 162660436 491466510 483493294 857962064 458323288 580317885 383628468 354171689 661032872 664815004 830467854 113445462 183765839 482728210 440276298 393243279 567914361 400265291 868500822 800405649 591884539 126987958 204487944 877258654 640186056 163514501 304926358 591036923 815625341 803930416 658349342 629734257 654261462 309442546 324853023 668911053 359248950 190634058 223902974 647041377 518699812 738030204 662179715 836243328 456377544 265473550 90354265 751040773 388742002 696188491 524141713 537657549 894116628 272158403 889429791 531065912 71498691 677830601 674133852 547103660 367944762 78452468 373581698 132516626 502194262 796096926 773938483 170022999 969009563 750103912 265196531 600925165 660381101 243807924 619985833 599579975 190603480 257888554 249064738 291173728 837576329 540261428 905075854 54265141 466410451 462151553 882772993 245925958 13593579 261789574 52823539 68721945 847568044 290356728 142091201 576340407 864663828 530569811 810752042 22832685 306859973 724471382 630581714 829849869 232033157 828056709 806477250 299528170 648604094 444055206 909286 248532447 895593215 42033732 811303310 794843657 439010169 394543919 232002029 513881096 690340226 957544954 408935581 763013763 857244694 624295548 463803930 2001825 216383825 447774800 424034370 945806224 846444790 793063765 344418523 601539841 363451627 138575918 368124429 849889194 143993275 469520578 978236132 913155779 457138450 790662845 397401551 184965002 496838725 739490830 106257188 88946623 904945352 390079335 61307802 921269288 841779381 104209088 47395533 855248142 91230540 487162325 658848189 627229886 927057773 904063651 372749647 783787530 639238688 451910639 384766154 582035654 167854349 546892735 659012188 995771979 191245572 164274142 319391123 599913974 322255479 356926044 267130341 363881898 437245435 220968460 785938216 553779274 409733323 890157829 807823898 799288384 159647045 322555170 590353114 785716729 518346090 247202434 831514477 732965479 639060322 5239304 474056250 658930046 669018102 290021340 589279886 2377399 271486229 686635496 926790425 990894479 205632591 226944603 663596655 454387721 855583581 86019626 551346057 913060648 106480279 713735050 596008001 135314294 175267196 864181367 509082073 867962240 210960174 319576369 896783221 513656920 278452467 214669498 520665244 605128722 245468853 365296473 568843707 794709575 538480515 890300697 355254434 500072597 212727310 554916938 947999493 326099228 257890093 729967615 844486396 236734210 105303129 155317391 710979971 394471665 763377713 284983317 381603067 708842388 809807608 583790832 417011111 327394333 573249298 830268995 975215664 821722818 448723339 494266998 730009122 945243963 299656336 393379763 900004972 290752838 854004211 246617194 919732708 124042532 73015211 258662349 591118273 101425177 39195730 543769685 178828319 393505007 296745893 212620347 532339327 419582580 487115528 553358336 103176772 88128503 311507967 100134629 704607030 45545935 596803766 266113908 224331779 706226132 686691962 794314741 146127033 698128868 308359742 574652153 367825230 524685919 709306135 272258516 271105048 821852844 654301888 218632474 745711701 401600434 58883095 934140713 585092773 392531039 399785374 559915679 792729482 605707813 547070459 885640416 644664303 584210808 127437432 34827409 993719710 986235473 594474372 866760736 283253192 309237934 812540208 998264889 33761666 990081295 483088306 939040338 504032322 157556987 384407525 850436384 991996006 270458233 946028488 819686688 28259757 959750552 755976955 614450959 838291388 360798439 516747589 370251890 331394714 605991933 905448208 421649935 808502068 538869490 14440939 999107186 686595546 313162724 563672839 793612394 738490048 964147060 418491835 54183305 130482302 418526534 860661761 867695783 49882769 667413125 619868406 607000671 191618519 152532572 69712221 525840272 801252119 228590206 734359581 424552413 363222903 724056478 162878143 322213422 749589252 818184184 868983793 326981421 494965038 172426695 429877253 844949450 821585224 633278412 266930034 206082488 480977164 401503182 765973330 881777133 557259030 899995412 173368803 44782374 622018916 490150125 991237894 419792992 607262172 49746728 342086339 180377440 477880518 390900892 150166979 624115500 570128718 634683298 872967637 940180112 822408195 620989077 282443881 879903899 787394907 337763417 960125208 797456671 14049325 800234194 9094170 744497460 540131893 437993320 789963470 21426613 331036307 904178057 166626870 918259649 917746764 977184551 889958776 671226171 738368712 34858806 15402590 634666315 978213970 283131439 254542295 615651548 17158300 67786384 200863860 699345691 234102584 660499290 720584427 445772798 403809311 247217298 645293208 77546683 342377518 4361664 684771831 14335564 288772005 661926003 808437547 258855922 201933478 493239994
672146043 905333167 235933628 706709420 157520591 87406794 232636497 610115042 887526967 201283663 97443126 618828280 780906596 93593997 415520543 249980175 799048493 694319766 813139748 854114638 788611340 310504130 642855746 107828316 116613023 433789740 977018584 266657768 370308135 673721651 412990251 27314722 731505164 861918459 761409506 882673215 509594967 354722282 776914314 391633656 314721590 740876075 975172115 765162251 414077563 672764974 104762705 308534713 180927518 187574566 337101692 293280583 439144375 520291209 20282800 731268989 241239044 471781524 559473262 400606250 547263337 988919237 884083737 360513437 406482539 139130719 155987322 806396205 445820980 625811177 965205053 595593139 851671315 295106991 282227570 81382411 705656057 156892992 995750412 345404823 842888188 47525870 620803941 337556667 154557655 937999185 344260024 536207714 292673896 256360132 493649062 259359095 601114417 748995559 416089010 415627117 483900377 264846619 680059077 205467320 237143464 58427401 199790762 629235794 646129166 936344092 104252307 241700151 409477660 51397378 72466834 765018345 714473737 33977134 257620257 147894764 482366638 284885593 461269915 446637643 951066123 604061693 805642176 351155730 679834048 571121113 987753525 861221841 222200980 355158128 303115266 505366816 431569906 506113417 752507154 851411733 79800423 563586224 596326582 130024655 275619366 638336436 535007266 429654511 670468996 465615655 316061423 537766682 21934971 444008161 626375064 967113336 119987755 86269566 113614845 521242680 303243605 238019547 42857954 100185866 744973535 260365725 262115185 169056931 375188818 381000618 908253620 385842749 273134687 22916525 987622172 721353492 845983062 411133846 824158205 53671658 230691757 946149400 965176079 810051715 260795263 709742890 931904495 336924202 438004746 630395015 846210459 634566187 218095664 339542573 256732410 310997335 917467895 187314402 541797714 621988227 13092361 396105386 775878352 687620616 673851957 642539858 861441796 340089925 411053548 35087593 447412578 849638424 499018180 873804353 325009858 357083753 997891833 806218610 970855136 739113888 916776935 746524760 6333148 306666538 207348369 355055376 642929084 84951799 340600093 326248575 632502758 341912063 794233942 947267787 41204902 276636856 439724073 958233568 684417710 901790882 915442216 188261868 813135504 364259259 753213962 199093731 812101958 213115659 994007081 191062011 686187691 563726618 22981122 343734833 874943488 866274933 651786937 708089539 548428392 127273517 383234450 69107892 771866987 747735639 798063225 486052428 27695479 199527053 187388027 57971605 578575962 408593003 355455563 341507807 772156362 708414995 442705598 568551740 530170845 583570090 200072015 503479557 71885713 76600024 305866908 451156563 820027205 105789772 418244838 491383687 902523198 690372918 280743061 403792322 581521956 820523211 269988530 621782893 715825026 82168773 701727084 762629811 532973129 753781728 884090004 849133570 766483789 373506398 49277984 17112718 340225478 742179204 218066603 928873678 164463057 183674139 353537523 775474429 194435821 938362096 86475099 754745242 355742847 983890516 891902567 629889000 623339086 252054428 186697026 718613615 302681863 712749218 768149819 250514297 161584826 551967554 403532611 294758806 796026203 626300894 69782641 378192408 701986626 716003803 783627390 355857304 737997739 69039138 391885898 735653999 485011767 859429792 932887637 655219518 108127849 933666758 187937094 187103591 187377194 520192777 412296808 619131281 581699142 348560227 521613864 953643559 111999981 620955344 850644120 490987482 612495923 429830098 631576047 59532827 438486672 282608110 463169287 502255010 130833248 879410221 260457438 271105258 797351011 473641884 151395349 451490482 930043199 901816268 414342516 565032061 807457273 932889938 959012964 94696211 551963520 728713288 630224499 206377726 395168290 194872522 279359188 886133518 396300309 750251898 160678620 823566038 852876272 54600189 755047558 925387052 246123823 642079612 890262768 856828588 101950642 805143332 877821660 572090422 223661886 25088166 469969200 138504556 213916154 184415928 927309174 74625333 192948980 442693009 19059805 502058045 205666202 386456433 140144182 327672178 244794177 429546263 691701624 564765320 371900834 736510025 62064956 214347894 936837976 434772048 400763841 125683703 600860771 266197113 61552361 815896075 84448423 69620373 788942010 980953715 709982318 452703097 327898591 672292408 344691938 180799871 542781477 627016740 886568084 470978820 658871038 915182407 244173304 514971880 25905665 967998324 518989286 675747601 93626216 215423425 183160347 527767784 968170128 898598667 958769078 666476506 672824957 175079023 48093115 536091096 368423507 914891730 408952723 466564055 375578590 244098651 836238218 523313233 10452491 346863859 474326864 102386627 255474029 158800588 578406521 860895533 691933369 681767895 542667517 443068053 537252682 283115340 727273400 34619780 540979101 988214310 548529387 341974407 751237078 640599460 616287929 973359279 697848378 495491018 745248683 967911953 816823219 919029214 602039597 517533767 652052559 675177195 399422991 668022766 22858689 680913473 151280900 562802726 563641311 17235443 413748006 958401301 855739170 446812503 389958256 39213668 599199529 52236682 423430211 709041088 802561846 945322474 543887330 27263834 140399791 976708250 546786549 943784552 969320862 44475649 513927178 845379490 195129138 95496779 274379023 665054149 41004604 966052838 69247962 565152276 259517875 550221831 134675105 897473234 884240688 126107683 160630914 351038921 794576755 667947894 892954620 698804934 931609308 568962943 84779892 186924058 266284018 668779138 176638386 129234715 458125792 665197061 234173025 860201633 624773875 439531347 595914898 283882377 879975197 351530492 568980281 564198197 137441909 40770131 995530671 717600266 586759093 43171823 648623150 681956850 280168635 931261482 853280856 740857560 360165128 196778661 294112177 216490798 81451076 424368066 145629216 728366697 410964152 343943976 41438322 50854276 309981650 269440067 363637463 85564281 859793573 492909762 155542371 882191819 488005222 935111447 599843470 323126528 633647856 726569210 619435445 377370911 729891137 974437351 954483095 922289206 553826811 264741787 964130008 202439382 834199524 672475803 521851521 137766037 940088422 715734701 113482366 602167435 290296847 565625692 490241055 740990933 568515346 779768952 19846807 488314390 184595909 820935316 690060160 396729841 788703521 305521031 935030102 167866256 698839365 497353451 326034423 622179616 310295028 2141345 830886185 145608018 309287186 167924043 860824340 62538204 831114538 617622225 384743108 84074998 20726763 829112029 686544552 305774302 317036710 55469919 46663958 459801172 306368210 273143561 727137989 895533854 10327689 627755987 644754769 919961990 867891464 647971704 148047802 490145239 576179507 128004088 570952933 276344547 414883854 360900628 693954586 784483968 950448453 704729045 502446468 478505478 44352421 805488390 661077684 626801363 590889888 368559029 156762911 287297223 803388878 594431158 718409371 406514888 703938406 978458656 981987814 637528895 517621449 935055310 558154527 706028698 460862456 178120159 87963723 519396296 320913689 92217142 278207953 648420544 764798198 732769786 489254654 816676602 585992573 150108183 515218562 602057716 647262785 87538108 95269105 65115054 155758327 311845852 529939780 473289006 679414266 268916397 158588245 932637438 34731720 824211499 511687270 533317545 687540867 516013206 63109019 918129729 872163954 141217007 590151803 215877852 913406589 965597055 680680819 587431698 260965811 268637777 948805203 359998081 30059208 381398963 754223311 947839817 686550159 846572729 50029823 415811217 577349765 449956282 877047775 358094080 260323654 248074961 348402128 983761220 242213653 135421533 328156437 12941967 900471385 952665473 915338839 404619028 836636186 268198053 316941090 778574479 948658824 262159347 803509861 661581498 262434676 930354139 685553910 569276889 102821589 590771599 208112140 633061679 375763781 770501000 595877315 666787718 460622466 750108671 868682140 901091244 924759021 41550708 495780602 497182960 88566542 493800747 583533989 494099881 68297742 862547370 769311307 805231023 490744379 821946685 274475770 594261216 42788488 471761522 382965672 120624029 418069514 877466781 410626219 266976586 218888828 31605845 250248001 360246481 360698556 878182901 889715210 180308768 303433036 918874652 291913096 29733286 57201874 390670382 591236774 365024474 156189848 576371920 163611438 462312628 985359116 415308399 58689106 998120754 770368065 279152570 835582244 177978069 127477357 226709540 176963357 255356193 786186857 329507939 818370202 167636256 355932724 864083700 541349722 131309024 695594352 890821268 581074690 666755312 873157603 47011016 282681241 388200167 137309176 349225558 86536716 471432158 513941308 20076490 46590123 465375216 57935585 184499698 375668650 821177281 931807294 381745250 764867489 420924148 337158988 329245169 786950157 173707956 44674859 181898042 277526988 908783148 551850139 928757532 474554277 603474703 842908803 868569403 807552190 670118417 267976814 756639357 738205476 554490219 957559561 390283661 105568839 636346203 546314407 97027419 81024378 411600034 996112829
